
//3573.买卖股票的最佳时机V
class Solution {
    typedef long long LL;
public:
    long long maximumProfit(vector<int>& prices, int k) {
        // 此题在原来的基础上,增加了一种状态:可以欠一张票
        // f表示有票 , g表示没票
        // f[i][j] = max(f[i-1][j] , g[i-1][j] - p[i] ,h[i-1][j-1] - p[i])
        // h[i][j] = max(h[i-1][j],f[i-1][j] + p[i])
        const int INF = -0x3f3f3f3f;        //表示最小值
        int n = prices.size();
        k = min(k,n/2);                     //如果price长度是n,最多交易n/2次,所以如果k太大是每必要的

        vector<vector<LL>> f(n,vector<LL>(k+1,INF));
        auto g = f , h = f;
        f[0][0] = -prices[0] , g[0][0] = 0 , h[0][0] = prices[0];
        for(int i = 1; i < n ;i++)
        {
            for(int j = 0 ;j <= k;j++)
            {
                f[i][j] = max(f[i-1][j] ,g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                h[i][j] = max(h[i-1][j] , g[i-1][j] + prices[i]);
                if(j - 1 >= 0) 
                    g[i][j] = max({g[i][j] , f[i-1][j-1] + prices[i], h[i-1][j-1] - prices[i]});
            }
        }
        return ranges::max(g[n-1]);
    }
};